package com.jinan.algorithm.dynamicProgramming;

import com.jinan.common.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class dpTest {
    //    DP三步
//    1. 思考回溯怎么写:
//        1.1. 入参和返回值
//        1.2. 递归到哪里
//        1.3. 递归边界和入口
//    2.改成记忆化搜索
//    3.翻译成递推，动态规划
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        System.out.println(Rob.rob1(nums));
        System.out.println(moveCharToEnd("abcde"));
        System.out.println(totalCombinations(4));
    }

    /**
     * 198. 打家劫舍 <a href="https://leetcode-cn.com/problems/house-robber/">...</a>
     * 难度： 简单
     * tag: 动态规划
     * description:
     * 如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
     * 给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。
     * restriction:
     * 1 <= nums.length <= 1000
     * 0 <= nums[i] <= 400
     *
     * @param nums 房屋存放金额的非负整数数组
     * @return int 偷窃到的最高金额
     * @apiNote 1. 思路：dp数组定义为dp[i]表示偷窃前i间房屋时，偷窃到的最高金额，
     * 状态转移方程：dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i])
     * 即为当前房屋偷窃到的最高金额等于（不选当前房屋）前i-1个房屋偷窃到的最高金额和（选当前房屋）当前房屋金额加上前i-2个房屋偷窃到的最高金额中的较大值
     * 边界条件：dp[0] = nums[0], dp[1] = Math.max(nums[0], nums[1]),以下代码中优化成了dp[2]=nums[0],dp[3]=Math.max(nums[0], nums[1])
     * 因为这样可以将边界条件合并到循环中，最后返回的是dp[nums.length + 1]
     */
    public static int rob(int[] nums) {
        int[] dp = new int[nums.length + 2];
        for (int i = 0; i < nums.length; i++) {
            dp[i + 2] = Math.max(dp[i + 1], dp[i] + nums[i]);
        }
        return dp[nums.length + 1];
    }

    public static int rob1(int[] nums) {
        int dp0 = 0, dp1 = 0;
        for (int num : nums) {
            int dp2 = Math.max(dp1, dp0 + num);
            dp0 = dp1;
            dp1 = dp2;
        }
        return dp1;
    }

    /**
     * 213. 打家劫舍 II <a href="https://leetcode-cn.com/problems/house-robber-ii/">...</a>
     * 难度： 中等
     * tag: 动态规划
     * description:
     * 房屋都 围成一圈,如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
     * 给定一个代表每个房屋存放金额的非负整数数组。计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
     *
     * @param nums 房屋存放金额的非负整数数组
     * @return int 偷窃到的最高金额
     * @apiNote 1. 思路：把这个问题分解为两个子问题，这样就把子问题退化为198题，198题的解法可以参考rob方法
     * 第一个子问题：偷窃nums[0]到nums[n-2]间房屋，第二个子问题：不偷nums[0],偷窃nums[1]到nums[n-1]间房屋，
     */
    public static int rob2(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        if (nums.length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        return Math.max(rob1(nums, 0, nums.length - 2), rob1(nums, 1, nums.length - 1));
    }

    private static int rob1(int[] nums, int start, int end) {
        int dp0 = nums[start], dp1 = Math.max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            int dp2 = Math.max(dp1, dp0 + nums[i]);
            dp0 = dp1;
            dp1 = dp2;
        }
        return dp1;
    }

    /**
     * 01背包问题
     *
     * @param w 物品重量
     * @param v 价值
     * @param c 背包容量
     * @return int 背包容量为c时，物品重量为w，价值为v的01背包问题中，返回最大价值
     */
    public static int knapsack(int[] w, int[] v, int c) {
        // dp数组定义为dp[i][j]表示拿前i个物品，背包容量为j时，拿到物品的最大价值，
        int n = w.length;
        int[][] dp = new int[n + 1][c + 1];

        // 初始化dp数组的第一行和第一列
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 0; // 当背包容量为0时，价值也为0
        }
        for (int j = 0; j <= c; j++) {
            dp[0][j] = 0; // 没有物品时，无论背包容量多少，价值都为0
        }

        // 动态规划填充dp数组
        for (int i = 1; i <= n; i++) { // 从1开始遍历物品
            for (int j = c; j >= w[i - 1]; j--) { // 注意这里w[i-1]，因为数组索引是从0开始的
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]); // 更新dp值
            }
        }
        return dp[n][c];

//        // 滚动数组
//        // dp数组定义为dp[i][j]表示拿前i个物品，背包容量为j时，拿到物品的最大价值，
//        int n = w.length;
//        int[] dp = new int[c + 1];
//        dp[0]=0;
//        // 动态规划填充dp数组
//        for (int i = 1; i <= n; i++) { // 从1开始遍历物品
//            for (int j = c; j >= w[i - 1]; j--) { // 注意这里w[i-1]，因为数组索引是从0开始的
//                dp[j] = Math.max(dp[j], dp[j - w[i - 1]] + v[i - 1]); // 更新dp值
//            }
//        }
//        return dp[c];
    }

    /**
     * 494. 目标和 <a href="https://leetcode-cn.com/problems/target-sum/">...</a>
     * 难度： 中等
     * tag: 数组 动态规划 回溯
     * description:
     * 给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
     * 返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
     * restriction:
     * 1 <= nums.length <= 20
     * 0 <= nums[i] <= 1000
     *
     * @param nums   非负整数数组
     * @param target 目标数
     * @return int 方法数
     * @apiNote 1. 思路：可以转化为01背包问题，背包容量为target，物品为nums，每个物品可以选0次或者选1次，每个物品的重量是nums[i]，每个物品的价值也是nums[i]
     * 在nums[i]数组中选择为正数的和为p，在nums[i]数组中数的和为s,那么为负数的和为s-p，那么p-(s-p)=target，p=(s+target)/2，那么问题就转化为01背包问题，
     * 枚举每个数选不选为正，选择的数的和要为p=(s+target)/2，那么问题就转化为01背包问题。
     */
    public int findTargetSumWays(int[] nums, int target) {
        int n = nums.length;
        for (int num : nums) {
            target += num;
        }
        if (target < 0 || target % 2 != 0) {
            return 0;
        }
        target /= 2;

        //滚动数组
//        int[] dp = new int[target + 1];
//        dp[0] = 1;
//        for (int num : nums) {
//            for (int i = target; i >= num; i--) {
//                dp[i] += dp[i - num];
//            }
//        }
//        return dp[target];

        int[][] dp = new int[n + 1][target + 1];
        dp[0][0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = target; j >= 0; j--) {
                if (j >= nums[i]) {
                    dp[i + 1][j] = dp[i][j] + dp[i][j - nums[i]];
                } else {
                    dp[i + 1][j] = dp[i][j];
                }
            }
        }
        return dp[n][target];
    }

    /**
     * 322. 零钱兑换 <a href="https://leetcode-cn.com/problems/coin-change/">...</a>
     * 难度： 中等
     * tag: 数组 动态规划
     * description:
     * 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回-1。
     * restriction:
     * 1 <= coins.length <= 12
     * 1 <= coins[i] <= 5000
     *
     * @param coins  硬币面额数组
     * @param amount 总金额
     * @return int 凑成总金额所需的最少的硬币个数
     * @apiNote 1. 思路：完全01背包，动态规划，dp[i]表示凑成金额i所需的最少的硬币个数，那么dp[i] = min(dp[i],dp[i-coins[j]]+1)
     */
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        for (int i = 1; i <= amount; i++) {
            dp[i] = amount + 1;
        }

        for (int coin : coins) {
            if (coin <= amount) {
                dp[coin] = 1;
            }
            for (int j = coin; j <= amount; j++) {
                dp[j] = Math.min(dp[j], dp[j - coin] + 1);
            }
        }
        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }

    /**
     * 1143. 最长公共子序列 <a href="https://leetcode-cn.com/problems/longest-common-subsequence/">...</a>
     * 难度： 中等
     * tag: 动态规划
     * description:
     * 给定两个字符串text1 和text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
     * 一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新
     * 字符串。
     * 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
     * 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
     * restriction:
     * 1 <= text1.length, text2.length <= 1000
     * text1 和 text2 仅由小写英文字符组成。
     *
     * @param text1 字符串1
     * @param text2 字符串2
     * @return int 最长公共子序列的长度
     * @apiNote 1. 思路：动态规划，dp[i][j]表示text1[0..i-1]和text2[0..j-1]的最长公共子序列的长度，
     */
    public int longestCommonSubsequence(String text1, String text2) {
        int n = text1.length();
        int m = text2.length();
        char[] chars1 = text1.toCharArray();
        char[] chars2 = text2.toCharArray();
        int[][] dp = new int[n + 1][m + 1];
        dp[0][0] = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (chars1[i] == chars2[j]) {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                } else {
                    dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]);
                }
            }
        }
        return dp[n][m];

        // 滚动数组
//        int n = text1.length();
//        int m = text2.length();
//        int[] dp = new int[m + 1];
//        dp[0] = 0;
//        for (int i = 1; i <= n; i++) {
//            for (int j = 1, pre = 0; j <= m; j++) {
//                int tmp = dp[j];
//                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
//                    dp[j] = pre + 1;
//                } else {
//                    dp[j] = Math.max(dp[j], dp[j - 1]);
//                }
//                pre = tmp;
//            }
//        }
//        return dp[m];
    }

    /**
     * 72. 编辑距离 <a href="https://leetcode-cn.com/problems/edit-distance/">...</a>
     * 难度： 困难
     * tag: 动态规划
     * description:
     * 给你两个单词word1 和word2，请你计算出将word1转换成word2 所使用的最少操作数。
     * 你可以对一个单词进行如下三种操作：
     * 插入一个字符
     * 删除一个字符
     * 替换一个字符
     * restriction:
     * 1 <= word1.length, word2.length <= 500
     * word1 和 word2 由小写英文字母组成
     *
     * @param word1 字符串1
     * @param word2 字符串2
     * @return int 最少操作数
     * @apiNote 1. 思路：动态规划，dp[i][j]表示word1[0..i-1]和word2[0..j-1]的最小编辑数，dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
     */
    public int minDistance(String word1, String word2) {
        int n = word1.length();
        int m = word2.length();
        char[] chars1 = word1.toCharArray();
        char[] chars2 = word2.toCharArray();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i <= m; i++) {
            dp[0][i] = i;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (chars1[i] == chars2[j]) {
                    dp[i + 1][j + 1] = dp[i][j];
                } else {
                    dp[i + 1][j + 1] = Math.min(Math.min(dp[i][j + 1], dp[i + 1][j]), dp[i][j]) + 1;
                }
            }
        }
        return dp[n][m];
    }

    /**
     * 300. 最长递增子序列 <a href="https://leetcode-cn.com/problems/longest-increasing-subsequence/">...</a>
     * 难度： 中等
     * tag: 动态规划
     * description:
     * 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
     * 示例 1：
     * 输入：nums = [10,9,2,5,3,7,101,18]
     * 输出：4
     * 示例 2：
     * 输入：nums = [0,1,0,3,2,3]
     * 输出：4
     * 示例 3：
     * 输入：nums = [7,7,7,7,7,7,7]
     * 输出：1
     * restriction:
     * 1 <= nums.length <= 2500
     * -104 <= nums[i] <= 104
     * 进阶：
     * 你可以设计时间复杂度为 O(n2) 的解决方案吗？
     *
     * @param nums 整数数组
     * @return int 最长递增子序列的长度
     * @apiNote 1. 思路：动态规划，dp[i]表示以nums[i]结尾的最长递增子序列的长度，dp[i] = max(dp[j]) + 1,j<i,nums[j]<nums[i]
     * 2. 思路2：贪心+二分查找，dp[i]表示以nums[i]结尾的最长递增子序列的长度，dp[i] = max(dp[j]) + 1,j<i,nums[j]<nums[i]
     */
    public int lengthOfLIS(int[] nums) {
        int ans = 0;
        int n = nums.length;
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }

    public int lengthOfLIS2(int[] nums) {
        int n = nums.length;
        int[] g = new int[n];
        g[0] = nums[0];
        int len = 1;
        for (int i = 1; i < n; i++) {
            int l = 0, r = len - 1;
            while (l <= r) { //[l,r)
                int mid = l + r >>> 1;
                if (g[mid] < nums[i]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            g[l] = nums[i];
            if (l == len) {
                len++;
            }
        }
        return len;
    }

    /**
     * 121. 买卖股票的最佳时机 <a href="https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/">...</a>
     * 难度： 简单
     * tag: 动态规划
     * description:
     * 给定一个数组 prices ，其中prices[i] 是一支给定股票第 i 天的价格。
     * 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
     * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
     * restriction:
     * 1 <= prices.length <= 3 * 10^4
     * 0 <= prices[i] <= 10^4
     * 1. 思路：动态规划，
     *
     * @param prices 股票价格数组
     * @return int 最大利润
     */
    public int maxProfit3(int[] prices) {
        int minPrice = prices[0];
        int maxProfit = 0;
        for (int price : prices) {
            minPrice = Math.min(minPrice, price);
            maxProfit = Math.max(maxProfit, price - minPrice);
        }
        return maxProfit;
    }

    /**
     * 122. 买卖股票的最佳时机 II <a href="https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/">...</a>
     * 难度： 中等
     * tag: 动态规划 贪心
     * description:
     * 给定一个数组 prices ，它的第i 个元素prices[i] 表示一支给定股票第 i 天的价格。
     * 在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
     * 返回 你能获得的 最大 利润 。
     * restriction:
     * 1 <= prices.length <= 3 * 104
     * 0 <= prices[i] <= 104
     *
     * @param prices 股票价格数组
     * @return int 最大利润
     * @apiNote 1. 思路：动态规划，状态机dp，dp[i][0]表示第i天不持有股票的最大利润，
     * dp[i][1]表示第i天持有股票的最大利润，
     * dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i]),dp[i][1] = max(dp[i-1][1],dp[i-])
     */
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n + 1][2];
        //初始化,因为状态转移要从前一天转移，边界条件就是0天，但是prices下标0是第1天。
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 0; i < n; i++) {
            dp[i + 1][0] = Math.max(dp[i][0], dp[i][1] + prices[i]);
            dp[i + 1][1] = Math.max(dp[i][1], dp[i][0] - prices[i]);
        }
        return dp[n][0];

//        int n = prices.length;
//        int maxProfit = 0;
//        for (int i = 1; i < n; i++) {
//            if (prices[i] > prices[i - 1]) {
//                maxProfit += prices[i] - prices[i - 1];
//            }
//        }
//        return maxProfit;
    }

    /**
     * 309. 最佳买卖股票时机含冷冻期 <a href="https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/">...</a>
     * 难度： 中等
     * tag: 动态规划 数组
     * description:
     * 给定一个整数数组prices，其中第 i 个元素代表了第 i天的股票价格 。你无法在第二天买入股票 (即冷冻期为 1 天)。
     * restriction:
     * 0 <= prices.length <= 5000
     * 0 <= prices[i] <= 1000
     *
     * @param prices 股票价格数组
     * @return int 最大利润
     */
    public int maxProfit2(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n + 2][2];
        //初始化,因为状态转移要从前2天转移，边界条件就是-1天，所以在dp数组最前面插入两个初始状态。dp[i]表示第i-1天的最大利润，
        dp[0][0] = 0;
        dp[1][1] = -prices[0];
        for (int i = 0; i < n; i++) {
            dp[i + 2][0] = Math.max(dp[i + 1][0], dp[i + 1][1] + prices[i]);
            dp[i + 2][1] = Math.max(dp[i + 1][1], dp[i][0] - prices[i]);
        }
        return dp[n + 1][0];
    }

    /**
     * 188. 买卖股票的最佳时机 IV <a href="https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/">...</a>
     * 难度： 困难
     * tag: 动态规划 数组
     * description:
     * 给你一个整数数组prices，其中prices[i]表示第i天的股票价格 。
     * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
     * restriction:
     * 1 <= k <= 100
     * 1 <= prices.length <= 1000
     * 0 <= prices[i] <= 1000
     *
     * @param k      交易次数
     * @param prices 股票价格数组
     * @return int 最大利润
     */
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        int[][][] dp = new int[n + 1][k + 1][2];
        for (int i = 0; i <= k; i++) {
            dp[0][i][0] = 0;
            dp[0][i][1] = -prices[0];
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i - 1]);
                dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i - 1]);
            }
        }
        return dp[n][k][0];
    }

    /**
     * 516. 最长回文子序列 <a href="https://leetcode-cn.com/problems/longest-palindromic-subsequence/">...</a>
     * 难度： 中等
     * tag: 动态规划 数组
     * description:
     * 给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。
     * 假设序列的长度不超过 1000。
     * restriction:
     * 1 <= s.length <= 1000
     *
     * @param s 字符串
     * @return int 最长回文子序列的长度
     * @apiNote 1. 思路：动态规划，区间dp，dp[i][j]表示s[i:j]的最长回文子序列的长度，
     * dp[i][j] = max(dp[i+1][j],dp[i][j-1]),dp[i][j] = dp[i+1][j-1]+2 if s[i]==s[j]
     */
    public int longestPalindromeSubseq(String s) {
        char[] chars = s.toCharArray();
        int n = chars.length;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (chars[i] == chars[j]) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][n - 1];
    }

    /**
     * 1039. 多边形三角剖分的最低得分 <a href="https://leetcode-cn.com/problems/minimum-score-triangulation-of-polygon/">...</a>
     * 难度： 中等
     * tag: 动态规划 数组
     * description:
     * 你有一个凸的 n 边形，其每个顶点都有一个整数值。给定一个整数数组 values ，其中 values[i] 是第 i 个顶点的值（即 顺时针顺序 ）。
     * 假设将多边形 剖分 为 n - 2 个三角形。对于每个三角形，该三角形的值是顶点标记的乘积，三角剖分的分数是进行三角剖分后所有 n - 2 个三角形的值之和。
     * 返回 多边形进行三角剖分后可以得到的最低分 。
     * restriction:
     * 3 <= values.length <= 50
     * 1 <= values[i] <= 100
     *
     * @param values 顶点值数组
     * @return int 最低分数
     * @apiNote 1. 思路：动态规划，区间dp，dp[i][j]表示s[i:j]的最小分数，dp[i][j] = min(dp[i][k]+dp[k][j]+values[i]*values[j]*values[k]) for k in i+1..j-1
     */
    public int minScoreTriangulation(int[] values) {
        int n = values.length;
        int[][] dp = new int[n][n];
        for (int i = n - 1; i >= 0; i--) {
            dp[i][i] = 0;
        }
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 2; j < n; j++) {
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = i + 1; k < j; k++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j] + values[i] * values[j] * values[k]);
                }
            }
        }
        return dp[0][n - 1];
    }

    /**
     * 543. 二叉树的直径 <a href="https://leetcode-cn.com/problems/diameter-of-binary-tree/">...</a>
     * 难度： 简单
     * tag: 动态规划 数组
     * description:
     * 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
     * restriction:
     * 1 <= 树的结点个数 <= 10000
     *
     * @param root 二叉树
     * @return int 二叉树的直径长度
     * @apiNote
     * @apiNote 2. 思路：递归，dfs，dfs(root) = max(dfs(root.left),dfs(root.right))+1
     */
    public int diameterOfBinaryTree(TreeNode<Integer> root) {
        dfs(root);
        return ans;
    }

    private int ans = 0;

    private int dfs(TreeNode<Integer> root) {
        if (root == null) {
            return -1;
        }
        int left = dfs(root.left) + 1;
        int right = dfs(root.right) + 1;
        ans = Math.max(ans, left + right);
        return Math.max(left, right);
    }

    /**
     * 124. 二叉树中的最大路径和 <a href="https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/">...</a>
     * 难度： 困难
     * tag: 动态规划 数组
     * description:
     * 给定一个非空二叉树，返回其最大路径和。
     * 本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
     * restriction:
     * 树中节点的数目范围是 [1, 3 * 104]
     * -1000 <= Node.val <= 1000
     *
     * @param root 二叉树
     * @return int 最大路径和
     * @apiNote 1. 思路：递归，dfs，dfs(root) = max(dfs(root.left),dfs(root.right))+root.val
     */
    public int maxPathSum(TreeNode<Integer> root) {
        maxPathSum2(root);
        return ans;
    }

    //    private int ans = Integer.MIN_VALUE;
    public int maxPathSum2(TreeNode<Integer> root) {
        if (root == null) {
            return 0;
        }
        int left = Math.max(0, maxPathSum2(root.left));
        int right = Math.max(0, maxPathSum2(root.right));
        int max = Math.max(left, right);
        ans = Math.max(ans, left + right + root.val);
        return max + root.val;
    }

    /**
     * 2246. 相邻字符不同的最长路径 <a href="https://leetcode-cn.com/problems/longest-path-with-different-adjacent-characters/">...</a>
     * 难度： 困难
     * tag: 动态规划 数组
     * description:
     * 给你一个字符串s，一个长度为n的parent数组，其中parent[i]是节点i的父节点。
     * 节点0为根节点。
     * 对于所有0 < i < n，节点i的连接方式为：parent[i] -> i 。
     * 返回从节点0到节点n-1之间，最长路径的长度。
     * restriction:
     * 2 <= s.length <= 105
     * 0 <= parent.length <= s.length - 1
     * parent.length == n - 1
     * 0 <= parent[i] <= n - 1 for all 1 <= i <= n - 1
     * parent[0] == -1
     * parent represents a valid tree.
     *
     * @param parent 父节点数组
     * @param s      字符串
     * @return int 最长路径长度
     */
    public int longestPath(int[] parent, String s) {
        int n = parent.length;
        this.chars = s.toCharArray();
        for (int i = 0; i < n; i++) {
            parentList.add(new ArrayList<>());
        }
        for (int i = 1; i < n; i++) {
            parentList.get(parent[i]).add(i);
        }
        longestPath2(0, -1);
        return ans + 1;
    }

    //    private int ans = 0;
    private final List<List<Integer>> parentList = new ArrayList<>();
    private char[] chars;

    public int longestPath2(int i, int j) {
        int maxlen = 0;
        for (int k : parentList.get(i)) {
            int klen = longestPath2(k, i) + 1;
            if (this.chars[k] != this.chars[i]) {
                ans = Math.max(ans, maxlen + klen);
                maxlen = Math.max(maxlen, klen);
            }
        }
        return maxlen;
    }

    /**
     * 337. 打家劫舍 III <a href="https://leetcode-cn.com/problems/house-robber-iii/">...</a>
     * 难度： 中等
     * tag: 动态规划 数组
     * description:
     * 在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。
     * 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵
     * 二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
     * 计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
     * restriction:
     * 1 <= nums.length <= 100
     * 0 <= nums[i] <= 400
     *
     * @param root 二叉树
     * @return int 最高金额
     * @apiNote 1. 思路：dfs，dfs(root) = max(dfs(root.left),dfs(root.right))+root.val
     */
    public int rob(TreeNode<Integer> root) {
        int[] robbed = rob2(root);
        return Math.max(robbed[0], robbed[1]);
    }

    public int[] rob2(TreeNode<Integer> root) {
        if (root == null) {
            return new int[]{0, 0};
        }
        int[] left = rob2(root.left);
        int[] right = rob2(root.right);
        int notSelect = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        int Select = root.val + left[0] + right[0];
        return new int[]{notSelect, Select};
    }

    /**
     * 968. 监控二叉树 <a href="https://leetcode-cn.com/problems/binary-tree-cameras/">...</a>
     * 难度： 困难
     * tag: 动态规划 数组
     * description:
     * 给定一个二叉树，我们在树的节点上安装摄像头。
     * 节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
     * 计算监控树的所有节点所需的最小摄像头数量。
     * restriction:
     * 1 <= 给定的二叉树的节点个数 <= 100
     *
     * @param root 二叉树
     * @return int 最小摄像头数量
     * @apiNote 1. 思路：dfs，分类讨论
     * 节点被监控到分为3种情况：1.装了摄像头，2.父节点被监控，3.子节点被监控
     * 2.思路：贪心，尽量使叶节点的监控,
     * 节点状态分为：0.无覆盖 1.有摄像头 2.有覆盖，但无摄像头
     */
    public int minCameraCover(TreeNode<Integer> root) {
        // 1.动态规划
        int[] res = minCameraCoverDfs(root);
        return Math.min(res[0], res[2]);
        // 2.贪心
//        if(minCameraCoverGreedy(root)==0){//root无覆盖
//            //安装摄像头
//            ans++;
//        }
//        return ans;
    }

    public int[] minCameraCoverDfs(TreeNode<Integer> root) {
        if (root == null) {
            return new int[]{Integer.MAX_VALUE / 2, 0, 0};
        }

        int[] left = minCameraCoverDfs(root.left);
        int[] right = minCameraCoverDfs(root.right);
        int choose = Math.min(left[0], left[1]) + Math.min(right[0], right[1]) + 1;
        int byFather = Math.min(left[0], left[2]) + Math.min(right[0], right[2]);
        int byChildren = Math.min(Math.min(left[0] + right[2], right[0] + left[2]), left[0] + right[0]);
        return new int[]{choose, byFather, byChildren};
    }

    //    private int ans=0;
    public int minCameraCoverGreedy(TreeNode<Integer> root) {
        // 0.无覆盖 1.有摄像头 2.有覆盖，但无摄像头
        // 空节点设置为2，有覆盖，但无摄像头设置
        if (root == null) {
            return 2;
        }
        int left = minCameraCoverGreedy(root.left);
        int right = minCameraCoverGreedy(root.right);
        if (left == 0 || right == 0) {
            ans++;
            return 1;
        }
        if (left == 1 || right == 1) {
            return 2;
        }
        if (left == 2 && right == 2) {
            return 0;
        }
        return -1;
    }

    /**
     * 70. 爬楼梯 <a href="https://leetcode-cn.com/problems/climbing-stairs/">...</a>
     * 难度： 简单
     * tag: 动态规划 数组
     * description:
     * 假设你正在爬楼梯。需要 n阶你才能到达楼顶。
     * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
     * 注意：给定 n 是一个正整数。
     * restriction:
     * 1 <= n <= 45
     *
     * @param n 楼层数
     * @return int 楼梯数
     * @apiNote 1. 思路：动态规划
     */
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    /**
     * 746. 使用最小花费爬楼梯 <a href="https://leetcode-cn.com/problems/min-cost-climbing-stairs/">...</a>
     * 难度： 简单
     * tag: 动态规划 数组
     * description:
     * 给定一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
     * 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
     * 找出达到楼梯顶部的最低花费。
     * restriction:
     * 2 <= cost.length <= 1000
     * 0 <= cost[i] <= 999
     *
     * @param cost 楼梯花费
     * @return int 最低花费
     * @apiNote 1. 思路：动态规划
     */
    public int minCostClimbingStairs(int[] cost) {
        //dp[i]表示cost[i]为入场费的情况下，从第i个台阶开始爬楼梯的最低花费
        int n = cost.length;
        int[] dp = new int[n + 2];
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < n; i++) {
            dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
        }
        return Math.min(dp[n - 1], dp[n - 2]);
    }

    public int minCostClimbingStairs2(int[] cost) {
        //dp[i]表示踏上第i个台阶的最小花费，不包括入场费
        int n = cost.length;
        int[] dp = new int[n + 2];
        dp[0] = 0;
        dp[1] = Math.min(cost[0], cost[1]);
        for (int i = 2; i < n; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i], dp[i - 2] + cost[i - 1]);
        }
        return dp[n - 1];
    }

    /**
     * 377. 组合总和 Ⅳ <a href="https://leetcode-cn.com/problems/combination-sum-iv/">...</a>
     * 难度： 中等
     * tag: 动态规划 数组
     * description:
     * 给定一个由 不同正整数组成的数组 nums ，和一个目标整数 target 。请从 nums 中找出并返回总和为 target 的元素组合的个数。
     * 数组中的数字可以在一次排列中出现任意次，但是顺序不同的序列被视作不同的组合。
     * restriction:
     * 1 <= nums.length <= 200
     * 1 <= nums[i] <= 1000
     * nums 中的所有元素 互不相同
     * 1 <= target <= 1000
     *
     * @param nums   数组
     * @param target 目标整数
     * @return int 组合总和个数
     * @apiNote 1. 思路：动态规划
     */
    public int combinationSum4(int[] nums, int target) {
        int len = nums.length;
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int num : nums) {
                if (i >= num) {
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp[target];
    }

    /**
     * 2466.统计构造好字符串的方案数
     * 难度：中等
     * tag: 动态规划 数学
     * description:
     * 给你整数 zero ，one ，low 和 high ，我们从空字符串开始构造一个字符串，每一步执行下面操作中的一种：
     * 将 '0' 在字符串末尾添加 zero  次。
     * 将 '1' 在字符串末尾添加 one 次。
     * 以上操作可以执行任意次。
     * 如果通过以上过程得到一个 长度 在 low 和 high 之间（包含上下边界）的字符串，那么这个字符串我们称为 好 字符串。
     * 请你返回满足以上要求的 不同 好字符串数目。由于答案可能很大，请将结果对 10^9 + 7 取余 后返回。
     * restriction:
     * 1 <= low <= high <= 10^5
     * 1 <= zero, one <= low
     *
     * @param low  字符串长度下界
     * @param high 字符串长度上界
     * @param zero 添加0的次数
     * @param one  添加1的次数
     * @return int 不同好字符串数目
     * @apiNote 1. 思路：动态规划
     */
    public int countGoodStrings(int low, int high, int zero, int one) {
        int mod = 1000000007;
        int[] dp = new int[high + 1];
        int ans = 0;
        dp[0] = 1;
        for (int i = 1; i <= high; i++) {
            if (i >= zero) {
                dp[i] = (dp[i] + dp[i - zero]) % mod;
            }
            if (i >= one) {
                dp[i] = (dp[i] + dp[i - one]) % mod;
            }
            if (i >= low) {
                ans = (ans + dp[i]) % mod;
            }
        }
        return ans;
    }

    /**
     * 2266.统计打字方案数
     * 难度：中等
     * tag: 动态规划 数学 字符串
     * description:
     * 给你一个字符串 pressedKeys ，其中每个字母代表一次 按键 操作，按位与运算符 & 的结果为 1 。
     * 请你返回按上述规则，字符串中 按位与运算符 & 的结果为 1 的 不同 非空字符串数目。
     * restriction:
     * 1 <= pressedKeys.length <= 10^5
     * pressedKeys 由大写英文字母组成
     *
     * @param pressedKeys 按键操作
     * @return int 不同非空字符串数目
     */
    public int countTexts(String pressedKeys) {
        int ans = 1;
        int count = 0;
        for (int i = 0; i < pressedKeys.length(); i++) {
            count++;
            char c = pressedKeys.charAt(i);
            if (i == pressedKeys.length() - 1 || c != pressedKeys.charAt(i + 1)) {
                if (c != '7' && c != '9') {
                    ans = (int) ((long) ans * f[count] % mod);
                } else {
                    ans = (int) ((long) ans * g[count] % mod);
                }
                count = 0;
            }
        }
        return ans;
    }

    private static final int mod = 1000000007;
    private static final int[] f = new int[100001];
    private static final int[] g = new int[100001];

    static {

        f[0] = g[0] = 1;
        f[1] = g[1] = 1;
        f[2] = g[2] = 2;
        f[3] = g[3] = 4;
        for (int i = 4; i <= 100000; i++) {
            f[i] = (int) (((long) f[i - 1] + f[i - 2] + f[i - 3]) % mod);
            g[i] = (int) (((long) g[i - 1] + g[i - 2] + g[i - 3] + g[i - 4]) % mod);
        }
    }

    /**
     * 45. 跳跃游戏 II <a href="https://leetcode.cn/problems/jump-game-ii/">...</a>
     * 难度：困难
     * tag: 动态规划 贪心
     * description:
     * 给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
     * 你的目标是使用最少的跳跃次数到达数组的最后一个下标。
     * 假设你总是可以到达数组的最后一个下标。
     * restriction:
     * 1 <= nums.length <= 104
     * 0 <= nums[i] <= 1000
     *
     * @param nums 数组
     * @return int 最少跳跃次数
     * @apiNote 1. 思路：动态规划
     */
    public int jump(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        for (int i = 1; i < n; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] >= i - j) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[n - 1];
    }

    /**
     * 740. 删除并获得点数 <a href="https://leetcode.cn/problems/delete-and-earn/">...</a>
     * 难度：中等
     * tag: 动态规划
     * description:
     * 给你一个整数数组 nums 。你可以选定任意整数作为删除元素，删除后剩余元素的得分为：
     * 删除的元素值与相邻元素（即下标与下标差为 1 的元素）的乘积之和。
     * 请你从数组中删除元素，并计算剩余元素的最高得分。
     * restriction:
     * 1 <= nums.length <= 2 * 10^4
     * 1 <= nums[i] <= 10^4
     *
     * @param nums 数组
     * @return int 最高得分
     * @apiNote 1. 思路：动态规划
     * 状态转移方程：dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1])
     */
    public int deleteAndEarn(int[] nums) {
        int n = nums.length;
        int max = Integer.MIN_VALUE;
        for (int num : nums) {
            max = Math.max(max, num);
        }
        int[] dp = new int[max + 1];
        int[] count = new int[max + 1];
        for (int num : nums) {
            count[num]++;
        }
        dp[0] = 0;
        dp[1] = count[1];
        for (int i = 2; i <= max; i++) {
            dp[i] = Math.max(dp[i - 2] + count[i] * i, dp[i - 1]);
        }
        return dp[max];
    }

    /**
     * LCR 166. 珠宝的最高价值 <a href="https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof/description/">...</a>
     * 难度：中等
     * tag: 动态规划
     * description:
     * 给定一个二维数组 frame ，其中 frame[i][j] 表示第 i 行第 j 列的宝石价值，返回所有宝石的最高价值。
     * 拿取珠宝的规则为：
     * 只能从架子的左上角开始拿珠宝
     * 每次可以移动到右侧或下侧的相邻位置
     * 到达珠宝架子的右下角时，停止拿取
     * 注意：珠宝的价值都是大于 0 的。除非这个架子上没有任何珠宝，比如 frame = [[0]]。
     * restriction:
     * 1 <= frame.length <= 10^3
     * 1 <= frame[i].length <= 10^3
     * 0 <= frame[i][j] <= 10^4
     *
     * @param frame 二维数组
     * @return int 最高价值
     * @apiNote 1. 思路：动态规划
     * dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])+frame[i][j]
     */
    public int jewelleryValue(int[][] frame) {
        int n = frame.length;
        int m = frame[0].length;
        int[][] dp = new int[n][m];
        dp[0][0] = frame[0][0];
        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i - 1][0] + frame[i][0];
        }
        for (int i = 1; i < m; i++) {
            dp[0][i] = dp[0][i - 1] + frame[0][i];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + frame[i][j];
            }
        }
        return dp[n - 1][m - 1];
    }

    /**
     * 410. 分割数组的最大值 <a href="https://leetcode.cn/problems/split-array-largest-sum/">...</a>
     * tag: 贪心 数组 二分查找 动态规划 前缀和
     * description:
     * 给定一个非负整数数组 nums 和一个整数 k，将数组分成 k 个非空的子数组。
     * 设计一个算法使得这 k 个子数组各自和的最大值最小。
     * restriction:
     * 1 <= k <= nums.length <= 1000
     * 0 <= nums[i] <= 10^6
     * 1 <= k <= min(50, nums.length)
     * @param nums 数组
     * @param k 分割的子数组个数
     * @return int 最小最大值
     */
//    public int splitArray(int[] nums, int k) {
//
//    }

    /**
     * 44. 通配符匹配 <a href="https://leetcode.cn/problems/wildcard-matching/">...</a>
     * 难度：困难
     * tag: 动态规划
     * description:
     * 给你一个字符串s和一个字符规律p，请你来实现一个支持 '?'和'*'的正则表达式匹配。
     * '?' 可以匹配任何单个字符。
     * '*' 可以匹配任意字符序列（包括空字符序列）。
     * 匹配应该不考虑字符串 s 和 p 中的大写和小写字母。
     * restriction:
     * 1 <= s.length, p.length <= 2000
     * s只包含从a-z的小写字母。
     * p只包含从a-z的小写字母，以及字符?和*。
     *
     * @param s 字符串
     * @param p 规则
     * @return boolean 是否匹配
     * @apiNote 1. 思路：动态规划
     */
    public boolean isMatch(String s, String p) {
        int n = s.length();
        int m = p.length();
        boolean[][] dp = new boolean[n + 1][m + 1];
        dp[0][0] = true;
        for (int i = 1; i <= m; i++) {
            if (p.charAt(i - 1) == '*' && dp[0][i - 1]) {
                dp[0][i] = true;
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                } else if (p.charAt(j - 1) == '?' || p.charAt(j - 1) == s.charAt(i - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
        return dp[n][m];
    }

    public static String moveCharToEnd(String S) {
        StringBuilder sb = new StringBuilder(S);
        int n = S.length();

        // 进行n次操作，每次将第i个字符移到末尾
        for (int i = 0; i < n; i++) {
            // 取出第i个字符
            char ch = sb.charAt(i);
            // 删除第i个字符
            sb.deleteCharAt(i);
            // 将取出的字符添加到字符串末尾
            sb.append(ch);
        }

        return sb.toString();
    }

    public static int countCombinations(int[] count, int sets, int pairs) {
        // 如果正好用了4个面子和1个对子，返回1表示找到一种组合
        if (sets == 4 && pairs == 1) {
            return 1;
        }
        // 如果已经用完所有牌但还没有达到4个面子+1个对子，返回0
        if (sets > 4 || pairs > 1) {
            return 0;
        }

        int res = 0;

        // 尝试刻子
        for (int i = 1; i <= 13; i++) {
            if (count[i] >= 3) {
                count[i] -= 3; // 使用刻子
                res += countCombinations(count, sets + 1, pairs); // 递归
                count[i] += 3; // 回溯
            }
        }

        // 尝试顺子
        for (int i = 1; i <= 11; i++) {
            if (count[i] >= 1 && count[i + 1] >= 1 && count[i + 2] >= 1) {
                count[i] -= 1; // 使用顺子的第一张
                count[i + 1] -= 1; // 使用顺子的第二张
                count[i + 2] -= 1; // 使用顺子的第三张
                res += countCombinations(count, sets + 1, pairs); // 递归
                count[i] += 1; // 回溯
                count[i + 1] += 1; // 回溯
                count[i + 2] += 1; // 回溯
            }
        }

        // 尝试对子
        if (pairs == 0) { // 只能选择一个对子
            for (int i = 1; i <= 13; i++) {
                if (count[i] >= 2) {
                    count[i] -= 2; // 使用对子
                    res += countCombinations(count, sets, pairs + 1); // 递归
                    count[i] += 2; // 回溯
                }
            }
        }

        return res;
    }

    public static int totalCombinations(int n) {
        int[] count = new int[14]; // 表示1~13号牌每种牌有n张
        for (int i = 1; i <= n; i++) {
            count[i] = 4; // 每种牌初始化为4张
        }
        return countCombinations(count, 0, 0);
    }

    /**
     * 55. 跳跃游戏 <a href="https://leetcode.cn/problems/jump-game/">...</a>
     * 难度：中等
     * tag: 动态规划
     * description:
     * 给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
     * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
     * 判断你是否能够到达最后一个下标。
     * restriction:
     * 1 <= nums.length <= 10^4
     * 0 <= nums[i] <= 10^5
     *
     * @param nums 数组
     * @return boolean 是否能到达最后一个下标
     */
    public boolean canJump(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, -1);
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            if (dp[i] >= 0) {
                for (int j = 1; j <= nums[i] && i + j < n; j++) {
                    dp[i + j] = dp[i + j] > 0 ? Math.min(dp[i + j], dp[i] + 1) : dp[i] + 1;
                }
            }
        }
        return dp[n - 1] >= 0;
    }

    public boolean canJump2(int[] nums) {
        int n = nums.length;
        int end = n-1;
        for (int i=end-1;i>=0;i--){
            if(i+nums[i]>=end){
                end = i;
            }
        }
        return end==0;
    }

    /**
     * 2327. 知道秘密的人数
     * 难度：中等
     * tag: 动态规划 队列 模拟
     * description:
     * 在第 1 天，有一个人发现了一个秘密。
     * 给你一个整数 delay ，表示每个人会在发现秘密后的 delay 天之后，每天 给一个新的人 分享 秘密。同时给你一个整数 forget ，表示每个人在发现秘密 forget 天之后会 忘记 这个秘密。一个人 不能 在忘记秘密那一天及之后的日子里分享秘密。
     * 给你一个整数 n ，请你返回在第 n 天结束时，知道秘密的人数。由于答案可能会很大，请你将结果对 10^9 + 7 取余 后返回。
     * restriction:
     * 2 <= n <= 1000
     * 1 <= delay < forget <= n
     * @param n 结果天数
     * @param delay 分享的延迟天数
     * @param forget 忘记的延迟天数
     * @return int 知道秘密的人数
     */
    public int peopleAwareOfSecret(int n, int delay, int forget) {
        int MOD = 1000000007;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for(int i=2;i<=n;i++){
            dp[i] = (dp[i-1] - dp[Math.max(i-forget,0)] + MOD) % MOD;
            if(i-delay>=0){
                dp[i] = (dp[i] + dp[i-delay]) % MOD;
            }
        }
        return (dp[n] - dp[n-forget] + MOD) % MOD;
    }
}
